/*
 * @lc app=leetcode.cn id=768 lang=typescript
 *
 * [768] 最多能完成排序的块 II
 */

// @lc code=start
function maxChunksToSorted(arr: number[]): number {
  // 记录区间的元素出现的频次
  const cnt = new Map<number, number>();
  const n = arr.length;

  const sortArr = [...arr];
  sortArr.sort((a, b) => a - b);

  let ans = 0;
  for (let i = 0; i < n; i++) {
    const x = arr[i];
    const y = sortArr[i];

    cnt.set(x, (cnt.get(x) || 0) + 1);
    if (cnt.get(x) === 0) cnt.delete(x);

    cnt.set(y, (cnt.get(y) || 0) - 1);
    if (cnt.get(y) === 0) cnt.delete(y);

    if (cnt.size === 0) ans++;
  }

  return ans;
}
// @lc code=end
